package com.lwl.Algorithmic_data_structure.class25单调栈;

import java.util.LinkedList;

/**
 * @author lwl
 * @Description 给你一个数组，代表一个多个长条的直方图，请你求出直方图中最大的矩形面积
 * @date 2023/6/26 8:38
 */
public class Code04LargestRectInHistogram {

    public static int getLargestRectInHistogram(int[] array) {
        LinkedList<Integer> stack = new LinkedList<>();
        int res = 0;
        for (int i = 0; i < array.length; i++) {
            while (!stack.isEmpty() && array[stack.peekLast()] >= array[i]) {
                int height = array[stack.pollLast()];
                int leftIndex = stack.isEmpty() ? 0 : stack.peekLast() + 1;
                int rightIndex = i - 1;
                int rect = (rightIndex - leftIndex + 1) * height;
                res = Math.max(rect, res);
            }
            stack.addLast(i);
        }
        while (!stack.isEmpty()) {
            int height = array[stack.pollLast()];
            int leftIndex = stack.isEmpty() ? 0 : stack.peekLast() + 1;
            int rightIndex = array.length - 1;
            int rect = (rightIndex - leftIndex + 1) * height;
            res = Math.max(rect, res);
        }
        return res;
    }

}
